//1.me --- rfind做法 ---最坏情况 O(n^2)
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ret;
      
        int left = 0;
        int right = 0;
        int ans =0;
        for(int i=0; i < s.size(); ++i) {
            //left默认为开头0
            right = max((int)s.rfind(s[i]), right);
           
            ans = max(right-left+1, ans);
            if(i == right) {
                ret.push_back(ans);
                ans = 0;                
                left = i+1;
            }

        }
        return ret;
    }
};

//2.优化存储一下字符最后出现位置----O(n)
class Solution {
public:
    vector<int> partitionLabels(string s) {
        vector<int> ret;
        int last[26]; // 每个字母最后出现的位置

        for(int i=0;i<s.size();++i) {
            last[s[i]-'a'] = i;
        }

        int left = 0;
        int right = 0;
        //int ans =0;
        for(int i=0; i < s.size(); ++i) {
            //left默认为开头0
            right = max(right, last[s[i]-'a']);
           
            //ans = right-left+1;
            if(i == right) {
                ret.push_back(right-left+1);                          
                left = i+1;
            }
        }

        return ret;
    }
};



